/*
70.爬楼梯
解法1：递归
解法2：动态规划思想，本质就是斐波那契数列，第三步开始，当前一步等于前两步之和
 */

public class LeeCode70 {

//    public int climbStairs(int n) {
//
//        if(n == 1) return 1;
//        if(n == 2) return 2;
//        return climbStairs(n-1) + climbStairs(n-2);
//    }
    public int climbStairs(int n){

        int p = 0;//第一步
        int q = 0;//第二步
        int r = 1;//第三步
        for (int i = 1; i <= n; i++) {
            p = q;
            q = r;
            r = p + q;

        }

        return r;
    }


    public static void main(String[] args) {

        System.out.println(new LeeCode70().climbStairs(2));
    }
}
/*
1    1
2    2
3    3
4    5
5    8

 */